Dynamic Memory Allocation
(Allocation and Release of variant size memory chunks)

You should have all taken the Data Structures class; many of you took it with Jeremy Ouellette.
In that class you probably discussed an algorithm used in memory management:
It involves a circular linked list of memory ‘chunks’ of variable size.
This algorithm is used by Operating Systems, so it is worth the reminder.

Assume a double linked list with a header (AVAIL) of variant size available memory, 
initialized by having all memory in one block.  
Records in use need TAG(1= inuse) at both beginning and end, 
SIZE at beginning, and UPLINK at end.  
Records available in addition need LLINK, RLINK at beginning.

See VariantFreeMemory.PDF for diagrams.

Interesting questions:
Should we always start at AVAIL, should we start each time where we left off before, or should we look through the whole list for the best fit?
(First fit versus next fit versus best fit)
If there is very little (<epsilon) left, should we just allocate the whole thing?
(internal fragmentation versus external fragmentation)
What should we do when no peace is large enough?
(Garbage collection & compaction)

Following are my notes, from when I taught Data Structures. 
//alloc free2
Assume a double linked list with a header (AVAIL) of variant size available memory, initialized by having all memory in one block.  Records in use need TAG(1= inuse) at both beginning and end, SIZE at beginning, and UPLINK at end.  Records available in addition need LLINK, RLINK at beginning.

Play with the IDEA.
Can you come up with a series of allocates and releases which cause :
First Fit to fail, but not next fit?
Next fit to fail, but not first fit?
What difference does it make, if you just allocate the whole block, 
if there is only a little bit left over?

Briefly write up your thoughts as a group.

Procedure allocate(size, pointer)
//first fit with epsilon
Ptr=avail->rlink           //arbitrary start point
Do{
            If ptr->size>=size then//big enough
                        {
                        Diff=ptr->size-size
                        If diff<epsilon//allocate whole block
                                    {
                                    Ptr->rlink->llink=ptr->llink
                                    Ptr->llink->rlink=ptr->rlink
                                    Ptr->tag=1
                                    (ptr+ptr->size-1)->tag=1
                                    (ptr+ptr->size-1)->uplink=ptr
                                    Return ptr
                                    }
                        Else     //allocate last SIZE words
                                    {
                                    Ptr->size=diff
                                    (ptr+diff-1)->uplink=ptr
                                    (ptr+diff-1)->tag=0
                                    Ptr=ptr+diff
                                    Ptr->size=size
                                    Ptr->tag=1
                                    (Ptr+size-1)->tag=1
                                    (Ptr+size-1)->uplink=ptr
                                    return
                                    }
                        }
Ptr=ptr->rlink
}while ptr!=avail
FAILURE

Procedure release(ptr)
//return a block
Size=ptr->size
If (ptr-1)->tag=1 and (ptr+size)->tag=1 //both adjacent blocks in use
            (ptr->tag)=0
            (ptr+size-1)->tag=0
            (ptr+size-1)->uplink=ptr
            Ptr->llink=avail
            Ptr->rlink=avail->rlink
            (ptr-rlink)->llink=ptr
            Avail->rlink=ptr
Else if (ptr-1)->tag=0  and (ptr+size)->tag=1  //only previous block free
            Ptr2=(ptr-1)->uplink//start of previous block
            Ptr2->size=ptr2->size+size
            (ptr+size-1)->uplink=ptr2
            (ptr+size-1)->tag=0
Else if  (ptr-1)->tag=1  and (ptr+size)->tag=0 //only following block free
            ((Ptr+ptr->size)->llink->rlink)=ptr
            ((Ptr+ptr->size)->rlink->llink)=ptr
            Ptr->llink=(ptr+size)->llink
            Ptr->rlink=(ptr+size)->rlink
            Ptr->size=size+(ptr+size)->size
            (ptr+ptr->size-1)->uplink=ptr
            Ptr->tag=0
Else //if  (ptr-1)->tag=0  and (ptr+size)->tag=0 //both adjacent blocks free
            ((ptr+size)->llink)->rlink=(ptr+size)->rlink//remove following block
            ((ptr+size)->rlink)->llink=(ptr+size)->llink
            Ptr2=(ptr-1)->uplink
            Ptr2->size=ptr2->size+size+(ptr+size)->size
            (ptr2+ptr2->size-1)->uplink=ptr2
return

Routine Release(PTR)
case: (ptr+size)->inuse=true AND (ptr-1)->inuse=true
 ptr->inuse=false
 (ptr+size-1)->inuse=false
 ptr->LLINK
 ptr->RLINK=AVAIL->RLINK
 AVAIL->RLINK=ptr
 (ptr->RLINK)->LLINK
case: (ptr+size)->inuse AND (ptr-1)->inuse=false
  (ptr+size-1)->inuse=false
  (ptr+size-1)->size=ptr+size+(ptr-1)->size
  location=ptr-(ptr-1)->size 
  location->size=ptr->size+(ptr-1)->size
case:(ptr+size)->inuse=false AND (ptr-1)->inuse
  ptr->inuse=false
  location=ptr+ptr->size
  ptr->size=ptr->size+location->size
  (ptr+ptr->size-1)->size=ptr->size
  ptr->LLINK = location->LLINK 
  ptr->RLINK=location->RLINK
  (ptr->LLINK)->RLINK=PTR
  (ptr->RLINK)->LLINK=PTR
case:(ptr+size)->inuse=false AND (ptr-1)->inuse=false
  ((ptr+size)->llink)->rlink=(ptr+size)->rlink//remove following block
  ((ptr+size)->rlink)->llink=(ptr+size)->llink
  ptr2=ptr-(ptr-1)->size//beginning of big block
  ptr2->size=ptr2->size+ptr->size+(ptr+size)->size //newsize = all 3
  (ptr2+ptr2->size-1)->size=ptr2->size